#
# @lc app=leetcode.cn id=10 lang=python3
#
# [10] 正则表达式匹配
#

# @lc code=start
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # dp[i][j]表示s长度为i,p长度j为是否匹配
        # if p[j]=='.' or p[j]==s[i]:
        #     dp[i][j] = dp[i-1][j-1]
        # elif p[j]=='*':
        #     if p[j-1]=='.' or p[j-1]==s[i]:
        #         # # *匹配0个
        #         # dp[i][j]=dp[i][j-2]
        #         # # *匹配1个
        #         # dp[i][j]=dp[i][j-1]
        #         # # *匹配多个
        #         # dp[i][j]=dp[i-1][j] # 没有理解此处
        #         dp[i][j] = dp[i][j-2] or dp[i][j-1] or dp[i-1][j]
        #     else:
        #         dp[i][j] = dp[i][j-2]

        n, m = len(s), len(p)
        dp = [[False]*(m+1) for _ in range(n+1)]
        # 初始化dp数组
        dp[0][0] = True
        dp[0][1] = False
        for j in range(2, m+1): # [2,m]
            if p[j-1] == "*":
                dp[0][j] = dp[0][j-2] # ???
        
        for i in range(1, n+1): # [1,n]
            for j in range(1, m+1): # [1,m]
                # 为什么p[j]
                # if p[j]=='.' or p[j]==s[i]:
                if p[j-1]=='.' or p[j-1]==s[i-1]:
                    dp[i][j] = dp[i-1][j-1]
                # elif p[j] == "*": 
                elif p[j-1] == "*":
                    # if p[j-1]=='.' or p[j-1]==s[i-1]:
                    if p[j-2]=='.' or p[j-2]==s[i-1]:
                        dp[i][j] = dp[i][j-2] or dp[i][j-1] or dp[i-1][j]
                    else:
                        dp[i][j] = dp[i][j-2]
        
        return dp[n][m]

# @lc code=end 

